`
https://leetcode.cn/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers/
`

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var numTriplets = function (nums1, nums2) {
  nums1.sort((a, b) => a - b)
  nums2.sort((a, b) => a - b)
  return count(nums1, nums2) + count(nums2, nums1)
};

// 传入的 nums 应当是有序的
// 找三元组 (i, j, j) 满足 nums1[i] ^ 2 == nums2[j] * nums2[k] 的个数
// 0 <= i < nums1.length 且 0 <= j < k < nums2.length
function count(nums1, nums2) {
  let res = 0

  // 枚举 i
  for (let i = 0; i < nums1.length; i++) {
    const target = nums1[i] ** 2
    // 双指针枚举 j 和 k
    let j = 0, k = nums2.length - 1
    while (j < k) {
      const s = nums2[j] * nums2[k]
      if (target === s) {
        if (nums2[j] === nums2[k]) {
          // 由于已排序，说明从 j 到 k 都相等
          // 从 j 到 k 选两个，组合公式 C(n, 2) = n * (n - 1) / 2
          const n = k - j + 1
          res += n * (n - 1) / 2
          break
        } else {
          // 分别统计
          const j0 = j
          j++
          while (j < k && nums2[j] === nums2[j - 1]) j++

          const k0 = k
          k--
          while (j0 < k && nums2[k] === nums2[k + 1]) k--

          res += (j - j0) * (k0 - k)
        }
      } else if (target > s) {
        j++
      } else {
        k--
      }
    }
  }

  return res
}